package Leetcode100Hot;

import java.util.ArrayDeque;
import java.util.Deque;

/*
柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4

提示：
1 <= heights.length <=105
0 <= heights[i] <= 104
 */
public class _86柱状图中最大的矩形 {

    //WA   超时  92/99
    public int largestRectangleArea(int[] heights) {
        int ret = 0;
        int n = heights.length;
        for (int i = 0; i < n; i++) {
            if (heights[i] == 0) {
                continue;
            }
            int hight = heights[i];
            int area = hight;
            for (int j = i - 1; j >= 0; j--) {
                hight = Math.min(heights[j], hight);
                if(hight == 0){
                    break;
                }
                area = Math.max(area, hight * (i - j + 1));
            }
            ret = Math.max(ret, area);
        }
        return ret;
    }


    //官解：方法一：单调栈
    //ps:这题考的基础模型其实就是：在一维数组中对每一个数找到第一个比自己小的元素。这类“在一维数组中找第一个满足某种条件的数”的场景就是典型的单调栈应用场景。
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/solutions/
     */
    class Solution {
        public int largestRectangleArea(int[] heights) {
            int n = heights.length;
            int[] left = new int[n];
            int[] right = new int[n];

            Deque<Integer> mono_stack = new ArrayDeque<Integer>();
            for (int i = 0; i < n; ++i) {
                while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                    mono_stack.pop();
                }
                left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
                mono_stack.push(i);
            }

            mono_stack.clear();
            for (int i = n - 1; i >= 0; --i) {
                while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                    mono_stack.pop();
                }
                right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
                mono_stack.push(i);
            }

            int ans = 0;
            for (int i = 0; i < n; ++i) {
                ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
            }
            return ans;
        }
    }

}
